home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / prolog / modprolg / mod-prol.lha / Prolog / Examples / chart.mod next >
Text File  |  1992-05-30  |  5KB  |  168 lines
  1. % Reference :
  2. % G.Gazdar and C.S.Mellish, "Natural Language Processing in Prolog : 
  3. %       An Introduction to Computational Linguistics", 1989, Addison-Wesley
  4.  
  5. signature agenda_sig =
  6.     sig
  7.         pred add_to_agenda/4 and remove_from_agenda/4 and 
  8.              erase_agenda/0 and agenda_data/4.
  9.     end.
  10.  
  11. structure agenda/agenda_sig =
  12.     struct
  13.         pred agenda_data/4.
  14.         add_to_agenda(V0,V1,C,Needed) :-
  15.             agenda_data(V0,V1,C,Needed) ->
  16.                 true ;
  17.                 asserta(agenda_data(V0,V1,C,Needed)).
  18.         remove_from_agenda(V0,V1,C,Needed) :-
  19.             retract(agenda_data(V0,V1,C,Needed)).
  20.         erase_agenda :-
  21.             retractall(agenda_data(_,_,_,_)).
  22.     end.
  23.  
  24. signature chart_sig =
  25.     sig
  26.         pred add_chart_edge/4 and erase_chart/0 and chart_edge/4.
  27.     end.
  28.  
  29. structure chart/chart_sig =
  30.     struct
  31.         pred chart_edge/4.
  32.         add_chart_edge(V0,V1,C,Needed) :-
  33.             chart_edge(V0,V1,C,Needed) ->
  34.                 true ;
  35.                 asserta(chart_edge(V0,V1,C,Needed)).
  36.         erase_chart :-
  37.             retractall(chart_edge(_,_,_,_)).
  38.     end.
  39.  
  40. signature grammar_sig =
  41.     sig
  42.         pred initial/1 and rule/2 and lex/2 and tag/1.
  43.     end.
  44.  
  45. structure grammar1/grammar_sig =
  46.     struct
  47.         tag(X) :-
  48.             current_structure(X).
  49.         initial(s).
  50.         rule(s,[np,vp]).
  51.         rule(np,[det,nb]).
  52.         rule(nb,[n]).
  53.         rule(nb,[n,rel]).
  54.         rule(rel,[wh,vp]).
  55.         rule(vp,[iv]).
  56.         rule(vp,[tv,np]).
  57.         rule(vp,[dv,np,pp]).
  58.         rule(vp,[sv,s]).
  59.         rule(pp,[p,np]).
  60.         lex(np,[kim]).
  61.         lex(np,[sandy]).
  62.         lex(np,[lee]).
  63.         lex(np,[bread]).
  64.         lex(det,[a]).
  65.         lex(det,[the]).
  66.         lex(det,[her]).
  67.         lex(n,[consumer]).
  68.         lex(n,[duck]).
  69.         lex(n,[man]).
  70.         lex(n,[woman]).
  71.         lex(wh,[who]).
  72.         lex(wh,[that]).
  73.         lex(p,[to]).
  74.         lex(iv,[died]).
  75.         lex(iv,[ate]).
  76.         lex(tv,[ate]).
  77.         lex(tv,[saw]).
  78.         lex(tv,[gave]).
  79.         lex(dv,[gave]).
  80.         lex(dv,[handed]).
  81.         lex(sv,[knew]).
  82.     end.
  83.  
  84. structure utils =
  85.     struct
  86.       % For each X do Y.
  87.         foreach(X,Y) :-
  88.             call(X),
  89.             do(Y),
  90.             fail.
  91.         foreach(_,_).
  92.         do(Y) :-
  93.             call(Y),!.
  94.       % Read in a sentence, terminated by a '.' and tag
  95.       % each word with Tag.
  96.         get_sentence(Wordlist,Tag) :-
  97.             get0(Char),
  98.             getrest(Char,Wordlist,Tag).
  99.         getrest(46,[],_) :- !.
  100.         getrest(32,Wordlist,Tag) :- !,
  101.             get_sentence(Wordlist,Tag).
  102.         getrest(Letter,[Word|Wordlist],Tag) :-
  103.             getletters(Letter,Letters,Nextchar),
  104.             name(Word,Letters,Tag),
  105.             getrest(Nextchar,Wordlist,Tag).
  106.         getletters(46,[],46) :- !.
  107.         getletters(32,[],32) :- !.
  108.         getletters(Let,[Let|Letters],Nextchar) :-
  109.             get0(Char),
  110.             getletters(Char,Letters,Nextchar).
  111.     end.
  112.  
  113. functor abs_parser(x/grammar_sig,y/agenda_sig,z/chart_sig) =
  114.     struct
  115.         inherit utils.
  116.         structure grammar = x.
  117.         structure agenda = y.
  118.         structure chart = z.
  119.  
  120.         start :-
  121.             agenda:erase_agenda,
  122.             chart:erase_chart,
  123.             grammar:tag(Tag),
  124.             utils:get_sentence(Sentence,Tag),
  125.             grammar:initial(Symbol),
  126.             start_agenda(Sentence,0),
  127.             start_active(Symbol,0),
  128.             expand_edges,
  129.             chart:chart_edge(0,_,Symbol,[]).
  130.             start_agenda([],_).
  131.  
  132.         start_agenda([Word|Words],V0) :-
  133.             V1 is V0 + 1,
  134.             utils:foreach(grammar:lex(Category,[Word]),
  135.                     agenda:add_to_agenda(V0,V1,Category,[])),
  136.             start_agenda(Words,V1).
  137.  
  138.         start_active(Category,Vertex) :-
  139.             utils:foreach(grammar:rule(Category,Categories),
  140.                     agenda:add_to_agenda(Vertex,Vertex,Category,Categories)).
  141.  
  142.         expand_edges :-
  143.             agenda:remove_from_agenda(V0,V1,Category,Needed) ,!,
  144.             extend_edges(V0,V1,Category,Needed).
  145.         expand_edges.
  146.  
  147.         extend_edges(V0,V1,Category,Needed) :-
  148.             chart:chart_edge(V0,V1,Category,Needed),
  149.             expand_edges.
  150.         extend_edges(V0,V1,Category,Needed) :-
  151.             chart:add_chart_edge(V0,V1,Category,Needed),
  152.             new_edges(V0,V1,Category,Needed),
  153.             expand_edges.
  154.  
  155.         new_edges(V1,V2,Category1,[]) :- 
  156.                       % Inactive edges
  157.             utils:foreach(chart:chart_edge(V0,V1,Category2,
  158.                                          [Category|Categories]),
  159.                     agenda:add_to_agenda(V0,V2,Category2,Categories)).
  160.         new_edges(V1,V2,Category1,[Category2|Categories]) :-
  161.                       % Active edges
  162.             start_active(Category2,V2),
  163.             utils:foreach(chart:chart_edge(V2,V3,Category2,[]),
  164.                     agenda:add_to_agenda(V1,V3,Category1,Categories)).
  165.     end.
  166.  
  167. structure final = abs_parser(grammar1,agenda,chart).
  168.